Polygonal shapes (curves and surfaces) are common choices for representing 2D and 3D models in the manufacturing, architectural, Geographic Information Systems, geoscience, warfare simulation, medical imaging, robotics, and entertainment industries.
It is frequently necessary to determine accurately the shortest distance to and closest point on such a shape from a given point or shape: this is important for instance in robotics in order to predict whether collisions between shapes are about to occur.
A shape typically is represented by either a polygonal curve or a polygonal surface. A polygonal curve has vertices connected by edges. A polygonal surface typically is represented by a triangular mesh which has vertices connected by triangles and edges. For a more detailed description, see U.S. patent application Ser. No. 006,771 entitled COMPRESSED REPRESENTATION OF CHANGING MESHES AND METHOD TO DECOMPRESS, filed Jan. 14, 1998 by G. Taubin and A. Gueziec, U.S. patent application Ser. No. 023,757, entitled PROGRESSIVE MULTI-LEVEL TRANSMISSION AND DISPLAY OF TRIANGULAR MESHES by A. Gueziec, G. Taubin and F. Lazarus, and U.S. patent application Ser. No. 976,247 entitled PROGRESSIVE COMPRESSION OF CLUSTERED MULTI-RESOLUTION POLYGONAL MODELS all of which are herein incorporated by reference in their entirety.
A query point is a point for which it is sought to compute the distance and closest point on one or more polygonal surfaces.
The problem of finding the shortest distance and closest point is very related to the problem of detecting intersections between shapes, because intersections are locations where such distances are zero. The problem of detecting intersections were recently studied by Ming Lin in "Efficient Collision Detection for Animation and Robotics", PhD Thesis, University of California, Berkeley, 1993, and by J. Klosowski et al., in "Efficient Collision Detection Using Bounding Volume Hierarchies of k-DOPS" in IEEE Transactions on Visualization and Computer Graphics, Vol 4. No. 1, January-March 1998, pages 21-36, all of which are herein incorporated by reference in their entirety. Other related work is described in the Lin and Klosowski's publications.
Ming Lin proposes a solution to find the shortest distance between a point and a convex shape and between two convex shapes. To generalize his solution to non-convex shapes, it is necessary to decompose non-convex shapes into convex shapes, which not only is known as a delicate operation by anyone versed in the field (there may be a high number of convex-subparts), but increases significantly the computational complexity of the method, because the computations must be performed on each shape separately. Another related method for finding closest pairs of points on convex shapes is described in U.S. Pat. No. 5,675,720 METHOD FOR SEARCHING FOR POINTS OF CLOSEST APPROACH AND PREPROCESSING METHOD THEREFOR. As with Ming Lin's method, this method does not easily generalize to solving the problem of finding a closest point on a non-convex shape. Klosowski's work does not generally apply to the problem of finding the closest point, but relates to finding the closest point as applied to an intersection or a touching.
Spatial data structures called quad-trees and Octrees can be used to solve a version of the same problem called Nearest Object location problem. For details, see p 228-9 of Applications of Spatial Data Structures, by H. Samet, Addison Wesley 1989. This problem is different because the shortest distance and closest point are not required in finding the closest object.
In U.S. Pat. No. 5,715,166 APPARATUS FOR THE REGISTRATION OF THREE-DIMENSIONAL SHAPES (which is herein incorporated by reference in its entirety), P. Besl and N. Mc Kay compute the distance from a query point to a three dimensional polygonal shape composed of triangles by computing the distances between the query point and each individual triangle (that is inside a min-max box defined in the vicinity of the query point) and by taking the minimum of the distances. This computation is expensive because the distance to each triangle composing, the shape is computed.